package 华为OD机试真题2023.基础题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ39_查找充电设备组合 {
  static int max_power;
  static int tmp = 0, res = 0;

  public static void main(String[] args) throws FileNotFoundException {
    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/39.txt"));
    int N = in.nextInt();
    int[] power = new int[N];
    for (int i = 0; i < N; i++) {
      power[i] = in.nextInt();
    }
    max_power = in.nextInt();
    dfs(power, 0);
    System.out.println(res);
  }

  static void dfs(int[] power, int cur) {
    if (tmp > max_power) {
      return;
    }
    if (cur == power.length) {
      res = Math.max(tmp, res);
      return;
    }
    // 选择该充电器
    tmp += power[cur];
    dfs(power, cur + 1);
    // 不选择该充电器
    tmp -= power[cur];
    dfs(power, cur + 1);
  }
}
